The present invention relates to a method for data decoding, and more particularly to a method which decodes data stored in a partial area of a coding pattern on a surface, based on a recorded image of the partial area, the coding pattern containing elements which each have at least two possible decoding values. The invention also relates to a device for data decoding, and more particularly to a data decoding device having a processing unit for decoding data which is stored in a partial area of a coding pattern on a surface. Moreover the invention relates to a memory medium on which is stored a computer program with instructions which, when executed by a processor, perform a method for data decoding based on an image. The invention also relates to a method of data decoding which performs decoding using probability calculations based on an image of a coding pattern.
In many situations it is desirable to be able to decode data stored in coded form on a product. One example of such data decoding is to determine the position on a surface provided with a coding pattern. Such position determination is useful, for instance, when using a reading pen on a writing surface.
Applicant""s Patent Publication WO 01/26032, which is herewith incorporated by reference, describes a device for position determination and a product that has a surface that is provided with a coding pattern. The device is arranged to record an image of the surface, to locate a predetermined number of symbols in the image, to determine the value of each of the symbols and to determine its position on the surface based on these values.
There are many other types of coding patterns in the form of position codes, for example, those in which each position is coded by a complex symbol with a special appearance.
A problem in decoding the known types of coding patterns is that the values of the symbols cannot always be determined with full accuracy. When the coding pattern is printed on a surface, the limited resolution of printers may imply that the symbols are not printed completely exactly. The symbols can, for example, be printed somewhat deformed or somewhat displaced from their xe2x80x9cnominalxe2x80x9d location. If it is the shape or location of the symbol that determines its value, the deformation and the displacement, respectively, mean that it may be difficult to determine the value of the symbol unambiguously.
It sometimes also happens that a symbol is not printed at all.
Another problem may arise if the coding pattern is printed on a surface that has a structure of its own that can interfere with the location of symbols in the recorded image. Structures in the surface can then be perceived as symbols by a device for data decoding. It can also happen that there are impurities, for instance in the form of dust, on the surface on which the coding pattern is printed. These impurities may give rise to noise symbols in the recorded image. Such noise symbols may then by mistake be identified as symbols in the coding pattern. Also, sensor noise from a sensor for recording the image may cause noise symbols in the image. Noise symbols in the recorded image may also originate from a defect on one of the components in the device, for instance damaged pixels in the sensor. On account of the above reasons there is therefore a risk that data cannot be decoded from the coding pattern in a recorded image.
According to a first aspect, the present invention relates to a method for decoding of data. The method according to this aspect of the invention decodes data stored in a partial area of a coding pattern on a surface, based on a recorded image of the partial area. The coding pattern contains elements, which each have at least two possible decoding values. The method identifies in the image a plurality of such elements, calculates, for each identified element, an associated value probability for each possible decoding value that the element has this decoding value, and decodes data based on the decoding values and the corresponding value probabilities.
For the reasons discussed above, the coding pattern on a surface, and/or the imaging of the same, is usually not completely perfect. One single decoding value for an element can usually not be determined with complete certainty as there is a possibility that the element has another of the possible decoding values. According to an aspect of the invention, for each element and for each of the decoding values, a value probability is therefore calculated that the element has that decoding value. If an element is determined unambiguously, then the value probability that corresponds to the unambiguously determined decoding value of the element will be maximum, while the other value probabilities for the element are zero. The more uncertain the decoding value of an element, the less difference there is between its value probabilities. If an element is missing in one place in the coding pattern, the value probabilities for the element will therefore be equally high. The present invention thus enables a relatively robust decoding of the coding pattern.
In the recorded image, more than a predetermined number of elements that are required for decoding of data may be identified according to one exemplary implementation of the present invention. The predetermined number of elements which may contribute most information in decoding can therefore be selected. As stated above, these elements are those having a dominating value probability for one of the decoding values. Consequently the chance increases that data can be decoded based on the recorded image since an element contributing little information can be sorted out.
The method may further comprise decoding at least a first set of decoding values for the predetermined number of identified elements.
The method may further comprise calculating sequence probabilities for a sequence of elements in the recorded partial area in the image. For instance, if the predetermined number of identified elements is a matrix, the sequence of elements can be the elements in a column or row in the matrix. The sequence probabilities can be calculated based on the value probabilities for the decoding values in the first set that correspond to the elements in the sequence. A value probability can be calculated for each of a plurality of a permissible combinations of decoding values. For each element, each of the possible decoding values corresponds to a value probability. The sequence probability for a combination may be determined based on the value probabilities for the decoding values which constitute the combination. In the same way as a value probability for an element corresponds to the element having the corresponding element value, a sequence probability for a sequence of elements corresponds to the sequence consisting of the corresponding combination. Of course, there are other ways than that described above in which sequence probabilities can be calculated.
The method may comprise selecting one of the possible decoding values for each of the elements which correspond to the first set of decoding values. The selection can be made based on a condition, given by the coding pattern, for the relation between the decoding values of the elements. The condition conveniently indicates which combinations of decoding values may exist among the elements in the coding pattern in the recorded image. In other words, the condition is given by how the used coding pattern is made up. The condition for existing combinations can be given at a global level, i.e., seen over all elements in the image, or at a local level, i.e., over an ensemble of elements in the image, for instance by columns and/or rows. Probability calculations are used to combine the information in the image, corresponding to the condition, so that the decoding values of the elements can be selected based on the probability calculations, within the scope of the condition.
The condition may indicate the above-discussed permissible combinations of decoding values.
Coding patterns that are used in connection with the present invention can usually be recorded xe2x80x9cfrom more than one directionxe2x80x9d. This means that the coding pattern in the recorded image can be rotated in different ways. The result of a decoding of data may depend upon the rotation of the coding pattern. For this reason, the method according to the invention may comprise carrying out the decoding based on rotation probabilities. The rotation probabilities correspond to different rotations or orientations of the recorded image, i.e., different rotations of the coding pattern. For each of the different rotations of the image, a rotation probability can be calculated. This can be done based on the sequence probabilities or value probabilities of the decoding values for the identified elements. Then data may be decoded based on the rotation of the coding pattern which gives the highest rotation probability. This step implies that the decoding of data is not affected by a device according to the invention being rotated in relation to the surface during the position determination.
According to a second aspect, the invention relates to a device for data decoding. The data decoding device according to this aspect of the invention includes a processing unit for decoding data which is stored in a partial area of a coding pattern on a surface, based on a recorded image of the partial area. The coding pattern contains elements, which each have at least two possible decoding values. The device is arranged to identify in the image a plurality of such elements, calculate for each identified element an associated value probability for each possible decoding value that the element defines this decoding value, and carry out decoding of data based on the decoding values and the corresponding value probabilities.
The image can be recorded by a sensor. The sensor can be integrated with the device for data decoding or be positioned in a separate unit, from which the device receives the recorded image.
According to a third aspect, the invention relates to a memory medium on which is stored a computer program with instructions which, when executed by a processor, perform a method for data decoding, based on an image.
According to a fourth aspect, the invention relates to a method of data decoding which performs decoding using probability calculations based on an image of a coding pattern.
Aspects of the present invention can be implemented as a computer program which is stored in the memory of the device and executed in the processor of the device or in an external device. Alternatively, the method can be implemented completely or partially in the form of an application-specific circuit, such as an ASIC, or in the form of digital or analog circuits or of some suitable combination thereof.
The features that are discussed in this application in connection with the disclosed data decoding technique are of course applicable to a method, a device and a memory medium according to the invention.
The features described in this application can of course be combined in the same embodiment.
Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.